from AutomataBuilder import *

class Determinizer():
    
    def __init__(self, a):
        self.s = a.s
        self.states = a.states
        self.final = a.final
        self.delta = a.delta

    def get_available_transitions(self):
        res = []
        for t, v in self.delta.items():
            if res.count(t[1])==0 and t[1]!="": 
                res.insert(0, t[1])

        #print "available_transitions " + str(res)
        return res


###########
    def stringuify_set_states(self, a):
        ret = AutomataBuilder()
        ret.set_initial(self.set_string(a.s))
        [ret.add_state(self.set_string(q)) for q in a.states]
        [ret.add_final(self.set_string(q)) for q in a.final]
        #print 's', a.s
        #print 'states', a.states
        #print 'final', a.final
        for k,v in a.delta.items():
            #print str(k[0]) + '-> (' + str(k[1]) + ') ' + str(v)
            ret.add_transition(self.set_string(k[0]), k[1], self.set_string(v))
        return ret

    def set_string(self, s):
        ret = ''
	a = list(s)
	a.sort()
        for q in a:
            ret = ret + q + '_'
        return ret[:-1]

    def determinize(self):
        ret = AutomataBuilder()
        current = self.l_closure_single(self.s)
        self.nexts = [current]

        ret.add_state(current)
        ret.set_initial(current)
        
        while len(self.nexts) > 0:
            current = self.nexts.pop()
            for x in self.get_available_transitions():
                new = set()
                for q in [q for q in current if (q,x) in self.delta]:
                    new = new.union([self.delta[(q,x)]])
                
                if len(new) == 0:
                    continue
                    
                new = self.l_closure(new)
                if not new in ret.states:
                    ret.add_state(new)
                    self.nexts.insert(0,new)
                ret.add_transition(frozenset(current), x, frozenset(new))
                
        self.set_final_states(ret)
        return ret

    def set_final_states(self, det):
        for qfo in self.final:
            for qs in det.states:
                if qfo in qs and qs not in det.final:
                    det.add_final(qs)
                    

    def l_closure(self, of_states):
        ret = set()
        for q in of_states:
            ret = ret.union(self.l_closure_single(q))
        return ret

    def l_closure_single(self, of_state):
        stack = [of_state]
        ret = set()
        visited = ret.copy()
        while len(stack) != 0:
            actual = stack.pop()
            visited.add(actual)
            ret.add(actual)
            for k,v in self.delta.items():
                # Filtro las que no son transiciones lambda y las que no salen de actual.
                if k[1] != '' or k[0] != actual:
                    continue
                for dest_state in v:
                    if dest_state in visited:
                        continue;
                    stack.append(dest_state)
        return ret
